import java.util.Objects;

class Person{
    public String id;

    public Person(String id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

public class HashBuck2<K,V> {

    static class Node<K,V> {
        public K key;
        public V val;
        public Node<K,V> next;

        public Node(K key,V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K,V>[] array;
    public int usedSize;

    public HashBuck2() {
        array = (Node<K,V>[])new Node[10];
    }


    public void put(K key,V val){
        int hash = key.hashCode();
        int index = hash % array.length;

        Node<K,V> cur = array[index];

        while(cur != null){
            if(cur.key.equals(key)){
                cur.val = val;
            }
            cur = cur.next;
        }

        Node<K,V> node = new Node<>(key,val);

        node.next = array[index];
        array[index] = node;
        usedSize++;


        if(loadFactor() > 0.75){
            resize();
        }

    }

    private void resize() {
        Node[] tmpArr = new Node[array.length * 2];
        //遍历原来的数组 将所有的元素    《重新哈希》到新的数组当中
        for (int i = 0; i < array.length; i++) {
            Node<K,V> cur = array[i];
            while (cur != null) {
                //记录当前节点的下个节点
                Node<K,V> curNext = cur.next;
                int hash = cur.key.hashCode();
                int newIndex = hash % tmpArr.length;

                //把原数组的值头插到新的数组
                cur.next = array[newIndex];
                tmpArr[newIndex] = cur;
                cur = curNext;
            }
        }
        array = tmpArr;

    }

    private double loadFactor() {
        return usedSize*1.0 / array.length;
    }



    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K,V> cur = array[index];
        while(cur != null){
            if((cur.key.equals(key))){
                return cur.val;
            }
            cur = cur.next;
        }

        return null;
    }
}
